package cn.edu.besti.cs2023.W2321;

public class HashSearch_Maru {
    public boolean hashSearch(int[] data,int target){
        int prime=0; //除留余数法
        for(int i= data.length;i>0;i--){
                if(isPrime(i)){
                    if (prime==0){
                        prime=i;
                    }
                }
            }
            Node[] hashtable= createHashTable(data,prime);
//        查找对应值
            int key=target%prime;
            Node cur=hashtable[key];
            while (cur!=null&&cur.key!=key){
                cur=cur.next;
        }
        if (cur==null){
            return false;
        }else {
            return  true;
        }
    }
    public Node[] createHashTable(int[] data,int allNode){
        Node[] hashtable=new Node[allNode];
        int key;
        for(int i=0;i<data.length;i++){
            Node node=new Node();
            node.key=data[i];
            key=data[i]%allNode;
            if(hashtable[key]==null){
                hashtable[key]=node;
            }else { //链地址法进行处理
                Node Next=hashtable[key];
                while (Next!=null&&Next.next!=null){
                    Next =Next.next;
                }
                Next.next=node;
            }
        }
        return hashtable;
    }
    public boolean isPrime(int index){
        for(int i=2;i<index;i++){
           if (index%i==0){
               return false;
           }
        }
        return true;
    }


}
class Node{

    int key;
    Node next;

}